//给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 
//
// 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "barfoothefoobarman", words = ["foo","bar"]
//输出：[0,9]
//解释：
//从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
//输出的顺序不重要, [9,0] 也是有效答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
//输出：[6,9,12]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 由小写英文字母组成 
// 1 <= words.length <= 5000 
// 1 <= words[i].length <= 30 
// words[i] 由小写英文字母组成 
// 
// Related Topics 哈希表 字符串 滑动窗口 
// 👍 601 👎 0


package leetcode.editor.cn.lc30;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class SubstringWithConcatenationOfAllWords{
    public static void main(String[] args){
        Solution solution = new Solution();
        List<Integer> res = solution.findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"});
        System.out.println(res);
    }
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> res = new ArrayList<>();

        int index = 0;
        Map<String, Integer> wordTable = new HashMap<>();
        for (String word : words) {
            if (!wordTable.containsKey(word)) {
                wordTable.put(word, index++);
            }
        }
        int[] wordCounts = new int[wordTable.size()];
        for (String word : words) {
            Integer idx = wordTable.get(word);
            wordCounts[idx]++;
        }

        int unitLen = words[0].length();
        for (int i = 0; i < unitLen; i++) {
            LinkedList<String> window = new LinkedList<>();
            int[] counts = new int[wordTable.size()];
            int mark = i;
            for (int j = i; j < s.length(); j+=unitLen) {
                if (j + unitLen > s.length()) {
                    break;
                }
                String substring = s.substring(j, j + unitLen);
                if (wordTable.containsKey(substring)) {
                    Integer idx = wordTable.get(substring);
                    if (counts[idx] < wordCounts[idx] ) {
                        window.offer(substring);
                        counts[idx]++;
                        if (Arrays.equals(counts, wordCounts)) {
                            res.add(mark);
                            String pop = window.pop();
                            counts[wordTable.get(pop)]--;
                            mark += unitLen;
                        }
                    }else {
                        window.offer(substring);
                        counts[idx]++;

                        while (true) {
                            String pop = window.pop();
                            counts[wordTable.get(pop)]--;
                            mark+=unitLen;
                            if (pop.equals(substring)) {
                                break;
                            }
                        }

                    }
                }else {
                    window.clear();
                    Arrays.fill(counts,0);
                    mark = j + unitLen;
                }
            }
        }

        return res;

    }

    public List<Integer> findSubstring2(String s, String[] words) {

        List<Integer> res = new ArrayList<>();

        Map<String, Long> wordMap = Arrays.stream(words).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        char[] chars = s.toCharArray();

        int unitLen = words[0].length();
        for (int i = 0; i < unitLen; i++) {
            LinkedList<String> window = new LinkedList<>();
            Map<String, Long> counts = new HashMap<>();
            int mark = i;
            for (int j = i; j < chars.length; j+=unitLen) {
                if (j + unitLen > chars.length) {
                    break;
                }
                String substring = s.substring(j, j + unitLen);
                if (wordMap.containsKey(substring)) {
                    if (counts.getOrDefault(substring,0L) < wordMap.get(substring) ) {
                        window.offer(substring);
                        counts.compute(substring, (k, old) -> old == null ? 1 : old + 1);
                        if (counts.equals(wordMap)) {
                            res.add(mark);
                            String pop = window.pop();
                            counts.compute(pop, (k, v) -> v - 1);
                            mark += unitLen;
                        }
                    }else {
                        window.offer(substring);
                        counts.compute(substring, (k, old) -> old == null ? 1 : old + 1);

                        while (true) {
                            String pop = window.pop();
                            counts.compute(pop, (k, old) -> old - 1);
                            mark+=unitLen;
                            if (pop.equals(substring)) {
                                break;
                            }
                        }

                    }
                }else {
                    window.clear();
                    counts.clear();
                    mark = j + unitLen;
                }
            }
        }

        return res;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

